洛谷试炼场 4-17 树链剖分

Diposting di | Edited on

[ZJOI2008]树的统计 （入门题,链最大值,链和）

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,q,a[maxn];
vector<int>G[maxn];
int size[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn];
int id[maxn],pre[maxn],cnt=0;
void dfs1(int u,int f,int deep){
    size[u]=1;
    fa[u]=f;son[u]=0;dep[u]=deep;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f)continue;
        dfs1(v,u,deep+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]])son[u]=v;
    }
}
void dfs2(int u,int root){
    id[u]=++cnt;top[u]=root;pre[cnt]=u;
    if(son[u])dfs2(son[u],root);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
int sumv[maxn<<2],maxv[maxn<<2];
inline void pushup(int o){
    sumv[o]=sumv[o<<1]+sumv[o<<1|1];
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}
void build(int o,int l,int r){
    int mid=(l+r)/2;
    if(l==r){
        sumv[o]=maxv[o]=a[pre[l]];return;
    }
    build(o<<1,l,mid);build(o<<1|1,mid+1,r);
    pushup(o);
}
void update(int o,int l,int r,int q,int v){
    int mid=(l+r)/2;
    if(l==r){
        sumv[o]=maxv[o]=v;return;
    }
    if(q<=mid)update(o<<1,l,mid,q,v);
    else update(o<<1|1,mid+1,r,q,v);
    pushup(o);
}
int querysum(int o,int l,int r,int ql,int qr){
    int mid=(l+r)/2,ans=0;
    if(ql<=l&&r<=qr)return sumv[o];
    if(ql<=mid)ans+=querysum(o<<1,l,mid,ql,qr);
    if(qr>mid)ans+=querysum(o<<1|1,mid+1,r,ql,qr);
    return ans;
}
int querymax(int o,int l,int r,int ql,int qr){
    int mid=(l+r)/2,ans=-inf;
    if(ql<=l&&r<=qr)return maxv[o];
    if(ql<=mid)ans=max(ans,querymax(o<<1,l,mid,ql,qr));
    if(qr>mid)ans=max(ans,querymax(o<<1|1,mid+1,r,ql,qr));
    return ans;
}
int qsum(int u,int v){
    int ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        ans+=querysum(1,1,n,id[top[u]],id[u]);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    ans+=querysum(1,1,n,id[v],id[u]);
    return ans;
}
int qmax(int u,int v){
    int ans=-inf;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        ans=max(ans,querymax(1,1,n,id[top[u]],id[u]));
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    ans=max(ans,querymax(1,1,n,id[v],id[u]));
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;G[u].push_back(v);G[v].push_back(u);
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    fa[1]=1;dfs1(1,0,1);dfs2(1,1);build(1,1,n);
    int q;
    cin>>q;
    while(q--){
        int x,y;char s[100];
        cin>>s>>x>>y;
        if(s[1]=='H')update(1,1,n,id[x],y);
        else if(s[1]=='M')cout<<qmax(x,y)<<endl;
        else if(s[1]=='S')cout<<qsum(x,y)<<endl;
    }
    return 0;
}

P2486 [SDOI2011]染色 (区间操作很难 未AC)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,q,col[maxn];
vector<int>G[maxn];
int size[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn];
int id[maxn],pre[maxn],cnt=0;
void dfs1(int u,int f,int deep){
    size[u]=1;
    fa[u]=f;son[u]=0;dep[u]=deep;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f)continue;
        dfs1(v,u,deep+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]])son[u]=v;
    }
}
void dfs2(int u,int root){
    id[u]=++cnt;top[u]=root;pre[cnt]=u;
    if(son[u])dfs2(son[u],root);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
struct node{
    int l,r;
    int num,lazy,lc,rc;
}my[maxn<<2];
void push_up(int o){
    my[o].lc=my[o<<1].lc;my[o].rc=my[(o<<1)|1].rc;
    int ans=my[o<<1].num+my[(o<<1)|1].num;
    if(my[o<<1].rc==my[(o<<1)|1].lc)ans--;
    my[o].num=ans;
}
void push_down(int o){
    if(my[o].lazy){
        my[o<<1].lazy=my[(o<<1)|1].lazy=my[o].lazy;
        my[o<<1].num=my[(o<<1)|1].num=1;
        my[o<<1].lc=my[o<<1].rc=my[o].lc;
        my[(o<<1)|1].lc=my[(o<<1)|1].rc=my[o].lc;
        my[o<<1].lazy=0;
    }
}
void build(int o,int l,int r){
    int mid=(l+r)/2;
    my[o].l=l;my[o].r=r;my[o].num=0;my[o].lazy=0;
    if(l==r){
        my[o].num=1;
        my[o].lc=my[o].rc=col[pre[l]];
        return;
    }
    build(o<<1,l,mid);build((o<<1)|1,mid+1,r);
    push_up(o);
}
void update(int o,int l,int r,int x){
    if(my[o].l==l&&my[o].r==r){
        my[o].num=my[o].lazy=1;
        my[o].lc=my[o].rc=x;
        return;
    }
    push_down(o);
    int mid=(my[o].l+my[o].r)/2;
    if(r<=mid)update(o<<1,l,r,x);
    else if(l>mid)update((o<<1)|1,l,r,x);
    else{
        update(o<<1,l,mid,x);update((o<<1)|1,mid+1,r,x);
    }
    push_up(o);
}
void uptree(int u,int v,int c){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update(1,id[top[u]],id[u],c);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    update(1,id[v],id[u],c);
}
int lc,rc;
int query(int o,int l,int r,int L,int R){
    if(my[o].l==L)lc=my[o].lc;
    if(my[o].r==R)rc=my[o].rc;
    if(my[o].l==l&&my[o].r==r)return my[o].num;
    push_down(o);
    int mid=(my[o].l+my[o].r)/2;
    if(r<=mid)return query(o<<1,l,r,L,R);
    else if(l>mid)return query((o<<1)|1,l,r,L,R);
    else{
        int ans=query(o<<1,l,mid,L,R);
        ans+=query((o<<1)|1,mid+1,r,L,R);
        if(my[o<<1].rc==my[(o<<1)|1].lc)ans--;
        return ans;
    }
    push_up(o);
}
int qutree(int u,int v){
    int ans1=-1,ans2=-1,ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v),swap(ans1,ans2);
        ans+=query(1,id[top[u]],id[u],id[top[u]],id[u]);
        if(rc==ans1)ans--;
        ans1=lc;u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v),swap(ans1,ans2);
    ans+=query(1,id[v],id[u],id[v],id[u]);
    if(rc==ans1)ans--;
    if(lc==ans2)ans--;
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>col[i];
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);G[v].push_back(u);
    }
    dfs1(1,1,1);dfs2(1,1);build(1,1,n);
    while(m--){
        char s[150];
        cin>>s;
        int x,y;
        if(s[0]=='C'){
            int c;cin>>x>>y>>c;
            uptree(x,y,c);
        }
        else{
            cin>>x>>y;
            cout<<qutree(x,y)<<endl;
        }
    }
    return 0;
}

P2146 [NOI2015]软件包管理器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,q,col[maxn];
vector<int>G[maxn];
int size[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn];
int id[maxn],pre[maxn],cnt=0;
void dfs1(int u,int f,int deep){
    size[u]=1;
    fa[u]=f;son[u]=0;dep[u]=deep;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f)continue;
        dfs1(v,u,deep+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]])son[u]=v;
    }
}
void dfs2(int u,int root){
    id[u]=++cnt;top[u]=root;pre[cnt]=u;
    if(son[u])dfs2(son[u],root);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
int sum[maxn<<2],lazy[maxn<<2];
void push_up(int o){
    sum[o]=sum[o<<1]+sum[o<<1|1];
}
void push_down(int o,int l,int r){
    if(lazy[o]){
        int mid=(l+r)/2;
        if(lazy[o]==-1)sum[o<<1]=sum[o<<1|1]=0,lazy[o<<1]=lazy[o<<1|1]=-1;
        else sum[o<<1]=mid-l+1,sum[o<<1|1]=r-mid,lazy[o<<1]=lazy[o<<1|1]=1;
        lazy[o]=0;
    }
}
void uninstall(int o,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){
        if(!x)lazy[o]=-1,sum[o]=0;
        else lazy[o]=1,sum[o]=r-l+1;return;
    }
    int mid=(l+r)/2;push_down(o,l,r);
    if(mid>=ql)uninstall(o<<1,l,mid,ql,qr,x);
    if(mid<qr)uninstall(o<<1|1,mid+1,r,ql,qr,x);
    push_up(o);
}
void install(int v,int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        uninstall(1,1,n,id[top[x]],id[x],v);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    uninstall(1,1,n,id[y],id[x],v);
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        int u;
        cin>>u;u++;
        G[i].push_back(u);
        G[u].push_back(i);
    }
    dfs1(1,1,1);
    dfs2(1,1);
    int m;cin>>m;
    char op[150];
    while(m--){
        int x;
        cin>>op>>x;x++;int p=sum[1];
        if(op[0]=='i'){
            install(1,x,1);
            cout<<abs(p-sum[1])<<endl;
        }
        else{
            uninstall(1,1,n,id[x],id[x]+size[x]-1,0);
            cout<<abs(p-sum[1])<<endl;
        }
    }
    return 0;
}
/*
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
*/

P3258 [JLOI2014]松鼠的新家 (区间加减)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>G[maxn];
int id[maxn],dep[maxn],pre[maxn],fa[maxn],size[maxn],son[maxn],cnt,top[maxn];
void dfs1(int now,int f,int deep){
    fa[now]=f;size[now]=1;son[now]=0;dep[now]=deep;
    for(auto i:G[now]){
        if(i==f)continue;
        dfs1(i,now,deep+1);
        size[now]+=size[i];
        if(size[i]>size[son[now]])son[now]=i;
    }
}
void dfs2(int now,int root){
    id[now]=++cnt;pre[cnt]=now;top[now]=root;
    if(son[now])dfs2(son[now],root);
    for(auto i:G[now]){
        if(i==fa[now]||i==son[now])continue;
        dfs2(i,i);
    }
}
int sum[maxn<<2],lazy[maxn<<2];
void push_up(int o){
    sum[o]=sum[o<<1]+sum[o<<1|1];
}
void push_down(int o,int l,int r){
    if(lazy[o]){
        int mid=(l+r)/2;
        lazy[o<<1]+=lazy[o];
        lazy[o<<1|1]+=lazy[o];
        sum[o<<1]+=(mid-l+1)*lazy[o];
        sum[o<<1|1]+=(r-mid)*lazy[o];
        lazy[o]=0;
    }
}
void update(int o,int l,int r,int ql,int qr,int w){
    int mid=(l+r)/2;
    if(ql<=l&&r<=qr){
        lazy[o]+=w;
        sum[o]+=(r-l+1)*w;
        return;
    }
    push_down(o,l,r);
    if(ql<=mid)update(o<<1,l,mid,ql,qr,w);
    if(qr>mid)update(o<<1|1,mid+1,r,ql,qr,w);
    push_up(o);
}
void print(int o,int l,int r,int ql,int qr){
    cout<<"o=="<<o<<" l="<<l<<" r="<<r<<" ql="<<ql<<" qr="<<qr<<endl;
    cout<<"sum="<<sum[o]<<endl;
}
int query(int o,int l,int r,int ql,int qr){
    //print(o,l,r,ql,qr);
    if(l==r){
        return sum[o];
    }
    int mid=(l+r)/2;
    push_down(o,l,r);
    if(ql<=mid)return query(o<<1,l,mid,ql,qr);
    else return query(o<<1|1,mid+1,r,ql,qr);
}
void uptree(int u,int v,int w){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update(1,1,cnt,id[top[u]],id[u],w);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    update(1,1,cnt,id[v],id[u],w);
}
int a[maxn];
// 适用于正负整数
template <class T>
inline bool read(T &ret)
{
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return 0; //EOF
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}
inline void out(int x)
{
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}
int main()
{
   /* std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);*/
    int n;
    //cin>>n;
    read(n);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
       // cin>>u>>v;
        read(u);read(v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1,1,1);dfs2(1,1);
    for(int i=1;i<n;i++){
        uptree(a[i],a[i+1],1);
        uptree(a[i+1],a[i+1],-1);
    }
    for(int i=1;i<=n;i++){
       // cout<<query(1,1,n,id[i],id[i])<<endl;
        out(query(1,1,n,id[i],id[i]));
        puts("");
    }
    return 0;
}